CHAP. XIV] METHODS OP FACTORING. 361
5p=t i. To express a number as x*+y2, subtract squares in turn and seek a remainder which is a square.
N. Beguelin29 proposed to find x such that 4pV-fl is a prime by excluding the values x making the sum composite. The latter is the case if
462+(2c+l)2, J
Set x =q+b/p. Then b is expressed rationally hi terms of c and the known p. Taking p = I, he derived a tentative process for finding a prime, of the form 4z2+l, which exceeds a given number a.
L. Euler30 proved that 10002+32 is prime since not expressible as a sum of two squares another way.
A. M. Legendre30a factored numbers represented as a sum of two squares in two ways.
J. P. Kulik's30Z> tables VIII and IX7 relating to the ending of squares, serve to test if 4n+ 1 is a sum of two squares and hence to test if it be prime or composite.
Th. Harmuth31 suggested testing a2-f 62 for factors, where a and 6 are relatively prime, by noting that it is divisible by 5 if a= =±= 1, b= =*= 2 (mod 5), and similar facts for p = 13, 17, 29, 37, there being p— 1 sets of values of a, b for each prime p=4n+l.
G. Wertheim32 explained in full Euler' s27 method of factoring.
R. W. D. Christie and A. Cunningham33 granted ]V = A2+52 and showed how to find a, . . ., d so that JV=(a2-f-62)(c2+d2). Similarly, if N = x2+Py2 in two ways.
FACTORING BY USB OF BINARY QUADRATIC FORMS.
L. Euler37 noted that a number is composite if it be expressible in two ways in the form/=aa;2+/fy2. The product of two numbers of the form/ is of the form g = a/5x2+2/2; the product of a number of the form / by one of the form g is of the form/. If for m>2 a composite number mp is expressible in a single way in the form /, there exist an infinitude of composite numbers mq expressible in a single way by /. He called (§34) a number N idoneal (numerus idoneus) if, for a/3=JVr, every number representable by /=ax2-f-/3y2 (with ax relatively prime to fiy) is a prime, the square of a prime, the double of a prime or a power of 2, so that a number representable by / in a single way is a prime. It suffices to test N-\-y2< 4N, y prime to N. He gave (§39, p. 208) the 65 idoneal numbers 1, 2, . . ., 1848 less than 10000.
"Nouv. M&n. Acad. Sc. Berlin, 1777, annee 1775, 300.
"Nova Acta Petrop., 10, 1792 (1778), 63; Comm. Arith., 2, 243-8.
aoaThe'orie des nombres, ed. 3, 1830, 1, 310. Simplification by Vuibert, Jour, de math.
10, p. '42. Cf. 1'interme'diaire des math.., 1, 1894, 167, 245; 18, 1911, 256. 8°6Tafeln der Quadrat und Kubik Zahlen ... bis hundert Tausend, Leipzig, 1848. 31Archiv Math. Phya., 67, 1882, 215-9. "Elemente der Zahlentheorie, 1887, 296-9. "Math. Quest. Educat. Times, (2), 11, 1907, 52-3, 65-7, 89-90. »7Nova Acta Petrop., 13, 1795-6 (1778), 14; Comm. Arith., 2, 198-214.